/*
*
* 归并排序：
* 主要思想： 分治，将原始数组划分成较小的数组，直到每个小数组只有一个位置，然后将小数组归并成较大的数组
* */

function mergeSort(arr){
    let len = arr.length;
    let array = [];
    if (len === 1){
        return arr;
    }else{
        let number = Math.floor(len/2);
        let left = arr.slice(0,number);
        let right = arr.slice(number);
        return merge(mergeSort(left),mergeSort(right));
    }
}

function merge(left,right){
    let l_len = left.length;
    let r_len = right.length;
    let l = 0;
    let r = 0;
    let arr = [];
    while(l_len > l && r_len > r){
        if (left[l] <= right[r]){
            arr.push(left[l]);
            l++;
        }else{
            arr.push(right[r]);
            r++;
        }
    }
    while(l < l_len){
        arr.push(left[l]);
        l++;
    }
    while(r < r_len){
        arr.push(right[r]);
        r++;
    }
    return arr
}

let array =  mergeSort([1,23,323,344,54,23,123,54,56,76,45,34,3432]);
console.log(array)
